package com.yun.algorithmproblem.leetcode;

public class Leetcode5 {

    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int[] res = new int[2];
        for (int i = 0; i < chars.length - 1; i++) {
            extend(chars, i, i, res);//一个字符作为中心点字符
            extend(chars, i, i + 1, res);//两个字符作为中心点字符
        }
        return new String(chars, res[0], res[1] - res[0] + 1);
    }

    private void extend(char[] chars, int i, int j, int[] res) {
        while (i >= 0 && j < chars.length
                && chars[i] == chars[j]) {//如果是回文,扩大回文范围
            i--;
            j++;
        }
        //不是回文
        i++;
        j--;
        if (j - i > res[1] - res[0]) {
            res[0] = i;
            res[1] = j;
        }
    }

    public String longestPalindrome1(String s) {
        char[] ch = s.toCharArray();
        int length = s.length();
        int[][] dp = new int[length + 1][length + 1];
        int[] maxNum = new int[2];
        for (int j = 0; j < length; j++) {
            for (int i = 0; i < length; i++) {
                if (ch[i] == ch[length - 1 - j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    if (dp[i + 1][j + 1] > maxNum[0]) {
                        if (i + j + 2 == length + dp[i + 1][j + 1]) {
                            maxNum[0] = dp[i + 1][j + 1];
                            maxNum[1] = i;
                        }
                    }
                }
            }
        }
        return new String(ch, maxNum[1] - maxNum[0] + 1, maxNum[0]);
    }

    public static void main(String[] args) {
        String s = "cbbd";
        Leetcode5 test = new Leetcode5();
        System.out.println(test.longestPalindrome(s));
    }
}
